package com.lun.easy;

import com.lun.util.BinaryTree.TreeNode;

public class IncreasingOrderSearchTree {
	
	//方法一：我写的，递归法
    public TreeNode increasingBST(TreeNode root) {
		if(root == null) return null;
    	
    	TreeNode left = increasingBST(root.left);
    	
    	if(left != null) {
	    	TreeNode p = left;
	    	
	    	while(p.right != null) {
	    		p = p.right;
	    	}
	    	
	    	p.right = root;
    	}
    	
    	root.left = null;
    	root.right = increasingBST(root.right);
    	
    	return left == null ? root : left;
    }
    
    //方法二：别人写的，递归法
    public TreeNode increasingBST2(TreeNode root) {
        return increasingBST2(root, null);
    }

    private TreeNode increasingBST2(TreeNode root, TreeNode tail) {
        if (root == null) return tail;
        TreeNode res = increasingBST2(root.left, root);
        root.left = null;
        root.right = increasingBST2(root.right, tail);
        return res;
    }
    
}
